package kmp;

import java.util.Arrays;

public class Main {
    /**
     * 获取子字符串的部分匹配值表
     * @param str
     * @return
     */
    public static int[] partialMatchingValue(String str) {
        int len = str.length();
        int[] values = new int[len];
        values[0] = 0;
        int i = 1;
        int j = 0; // 控制相同部分的长度
        while (i < len) {
            if (str.charAt(i) == str.charAt(j)) {
                j ++; // 长度加一
                values[i] = j; // 让这一次的前缀后缀最大长度为j
                i ++; // 当这两个字母相等时可以比较下一个字母了
            } else {
                // 需要限定长度大于0
                if (j > 0) {
                    j = values[j - 1]; // 让长度等于上一步的公共长度，然后再次比较
                } else {
                    // 当两个字母不相等且无法再退
                    values[i] = j; // 为零
                    i ++;
                }
            }
        }
        return values;
    }

    /**
     * 给部分匹配值做移位方便做运算
     * @param values
     * @return
     */
    public static void move(int[] values) {
        for (int i = values.length - 1; i > 0; i--) {
            values[i] = values[i - 1];
        }
        values[0] = -1;
    }

    public static boolean hasStr2(String str1, String str2, int[] values) {
        if (str1 == null && str2 == null) {
            return false;
        }
        if (str1.length() < str2.length()) {
            return false;
        }
        if (str2 == null) {
            return true;
        }
        int i = 0;
        int j = 0;
        while (i < str1.length()) {
            if (str1.charAt(i) == str2.charAt(j)) {
                i ++;
                j ++;
            } else {
                j = values[j];
                if (j == -1) {
                    // j退到了str1的0位置，都实行加加
                    i ++;
                    j ++;
                }
            }
            if (j == str2.length()) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
//        String str1 = "ABABABABCABAAB";
        String str2 = "ABCABB";
        int[] values = partialMatchingValue(str2);
//        move(values);
//        System.out.println(hasStr2(str1, str2, values));
        System.out.println(Arrays.toString(values));
    }
}
